Keyword: graph coloring

Found 22 papers in total
Incidence coloring of Cartesian product graphs
Incidence coloring of Cartesian product graphs
2015,
For a vertex v∈V(G), the incidence neighborhood of v, denoted by IN(v), is the...
Vertex coloring edge-weighted digraphs
Vertex coloring edge-weighted digraphs
2015,
A coloring of a digraph with non‐negative edge weights is a partition of the...
Multi‐coloring and job‐scheduling with assignment and incompatibility costs
Multi‐coloring and job‐scheduling with assignment and incompatibility costs
2013,
Consider a scheduling problem ( P ) which consists of a set of jobs to be performed...
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
2014,
A k ‐colouring of a graph G =( V , E ) is a mapping c : V →{1,2,…,...
On some geometric problems of color‐spanning sets
On some geometric problems of color‐spanning sets
2013,
In this paper we study several geometric problems of color‐spanning sets: given...
From Holant to #CSP and Back: Dichotomy for Holantc Problems
From Holant to #CSP and Back: Dichotomy for Holantc Problems
2012,
We explore the intricate interdependent relationship among counting problems,...
Equivalence of two conjectures on equitable coloring of graphs
Equivalence of two conjectures on equitable coloring of graphs
2013,
A graph G is said to be equitably k ‐colorable if there exists a proper k...
Enumerating the edge‐colourings and total colourings of a regular graph
Enumerating the edge‐colourings and total colourings of a regular graph
2013,
In this paper, we are interested in computing the number of edge colourings and total...
Acyclic edge coloring of planar graphs without 4‐cycles
Acyclic edge coloring of planar graphs without 4‐cycles
2013,
An acyclic edge coloring of a graph G is a proper edge coloring such that no...
Colorability of mixed hypergraphs and their chromatic inversions
Colorability of mixed hypergraphs and their chromatic inversions
2013,
We solve a long‐standing open problem concerning a discrete mathematical model,...
3‐Colouring AT‐Free Graphs in Polynomial Time
3‐Colouring AT‐Free Graphs in Polynomial Time
2012,
Determining the complexity of the colouring problem on AT‐free graphs is one of...
Algorithms for recognizing bipartite‐Helly and bipartite‐conformal hypergraphs
Algorithms for recognizing bipartite‐Helly and bipartite‐conformal hypergraphs
2011,
A hypergraph is Helly if every family of hyperedges of it, formed by pairwise...
Algorithms for Coloring Quadtrees
Algorithms for Coloring Quadtrees
2002,
We describe simple linear time algorithms for coloring the squares of balanced and...
Almost Exact Matchings
Almost Exact Matchings
2012,
In the exact matching problem we are given a graph G , some of whose edges are colored...
A wide‐ranging computational comparison of high‐performance graph colouring algorithms
A wide‐ranging computational comparison of high‐performance graph colouring algorithms
2012,
This paper reviews the current state of the literature surrounding methods for the...
A new DSATUR‐based algorithm for exact vertex coloring
A new DSATUR‐based algorithm for exact vertex coloring
2012,
This paper describes a new exact algorithm PASS for the vertex coloring problem based...
On compact k‐edge‐colorings: A polynomial time reduction from linear to cyclic
On compact k‐edge‐colorings: A polynomial time reduction from linear to cyclic
2011,
A k ‐edge‐coloring of a graph G = ( V , E ) is a function c that assigns...
Quadratic Kernelization for Convex Recoloring of Trees
Quadratic Kernelization for Convex Recoloring of Trees
2011,
The Convex Recoloring (CR) problem measures how far a tree of characters differs from...
Approximation Algorithms for the Interval Constrained Coloring Problem
Approximation Algorithms for the Interval Constrained Coloring Problem
2011,
We consider the interval constrained coloring problem, which appears in the...
Injective Colorings of Graphs with Low Average Degree
Injective Colorings of Graphs with Low Average Degree
2011,
Let mad( G ) denote the maximum average degree (over all subgraphs) of G and let χ...
Testing Convexity Properties of Tree Colorings
Testing Convexity Properties of Tree Colorings
2011,
A coloring of a graph is convex if it induces a partition of the vertices into...
Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
2011,
Let T = ( V , A ) be a directed tree. Given a collection 𝒫 of dipaths on T , we...
Papers per page: