On classes of minimal circular-imperfect graphs

Circular-perfect graphs form a natural superclass of perfect graphs: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ-bound graphs with the smallest non-trivial χ-binding function χ(G)?ω(G)+1.The Strong Perfect Graph Conjecture, recently settled by Chudnovsky et al. [The strong perfect graph theorem, Ann. of Math. 164 (2006) 51-229], provides a characterization of perfect graphs by means of forbidden subgraphs. It is, therefore, natural to ask for an analogous conjecture for circular-perfect graphs, that is for a characterization of all minimal circular-imperfect graphs.At present, not many minimal circular-imperfect graphs are known. This paper studies the circular-(im)perfection of some families of graphs: normalized circular cliques, partitionable graphs, planar graphs, and complete joins. We thereby exhibit classes of minimal circular-imperfect graphs, namely, certain partitionable webs, a subclass of planar graphs, and odd wheels and odd antiwheels. As those classes appear to be very different from a structural point of view, we infer that formulating an appropriate conjecture for circular-perfect graphs, as analogue to the Strong Perfect Graph Theorem, seems to be difficult.     

Injective colorings of planar graphs with few colors

An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ-colorable. We also show that all planar graphs of girth ≥ 10 are injectively (Δ+1)-colorable, that Δ+4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable.     

Linear choosability of graphs

A proper vertex coloring of a non-oriented graph G is linear if the graph induced by the vertices of any two color classes is a forest of paths. A graph G is linearly L-list colorable if for a given list assignment L={L(v):v∈V(G)}, there exists a linear coloring c of G such that c(v)∈L(v) for all v∈V(G). If G is linearly L-list colorable for any list assignment with |L(v)|?k for all v∈V(G), then G is said to be linearly k-choosable. In this paper, we investigate the linear choosability for some families of graphs: graphs with small maximum degree, with given maximum average degree, outerplanar and planar graphs. Moreover, we prove that deciding whether a bipartite subcubic planar graph is linearly 3-colorable is an NP-complete problem.     

On 3-choosable planar graphs of girth at least 4

Let G be a plane graph of girth at least 4. Two cycles of G are intersecting if they have at least one vertex in common. In this paper, we show that if a plane graph G has neither intersecting 4-cycles nor a 5-cycle intersecting with any 4-cycle, then G is 3-choosable, which extends one of Thomassen’s results [C. Thomassen, 3-list-coloring planar graphs of girth 5, J. Combin. Theory Ser. B 64 (1995) 101-107].     

Acyclic 5-choosability of planar graphs without 4-cycles

A proper vertex coloring of a graph G=(V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L-list colorable if for a given list assignment L={L(v):v∈V}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L-list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k-choosable. In this paper we prove that every planar graph without 4-cycles and without two 3-cycles at distance less than 3 is acyclically 5-choosable. This improves a result in [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (2006) 281-300], which says that planar graphs of girth at least 5 are acyclically 5-choosable.     

Complexity of two coloring problems in cubic planar bipartite mixed graphs

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].     

Efficient algorithms for finding critical subgraphs

This paper presents algorithms to find vertex-critical and edge-critical subgraphs in a given graph G, and demonstrates how these critical subgraphs can be used to determine the chromatic number of G. Computational experiments are reported on random and DIMACS benchmark graphs to compare the proposed algorithms, as well as to find lower bounds on the chromatic number of these graphs. We improve the best known lower bound for some of these graphs, and we are even able to determine the chromatic number of some graphs for which only bounds were known.     

Invalid proofs on incidence coloring

Incidence coloring of a graph G is a mapping from the set of incidences to a color-set C such that adjacent incidences of G are assigned distinct colors. Since 1993, numerous fruitful results as regards incidence coloring have been proved. However, some of them are incorrect. We remedy the error of the proof in [R.A. Brualdi, J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58] concerning complete bipartite graphs. Also, we give an example to show that an outerplanar graph with Δ=4 is not 5-incidence colorable, which contradicts [S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397-405], and prove that the incidence chromatic number of the outerplanar graph with Δ≥7 is Δ+1. Moreover, we prove that the incidence chromatic number of the cubic Halin graph is 5. Finally, to improve the lower bound of the incidence chromatic number, we give some sufficient conditions for graphs that cannot be (Δ+1)-incidence colorable.     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

On resistance of graphs

An edge-coloring of a graph G with integers is called an interval coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. It is known that not all graphs have interval colorings, and therefore it is expedient to consider a measure of closeness for a graph to be interval colorable. In this paper we introduce such a measure (resistance of a graph) and we determine the exact value of the resistance for some classes of graphs.     

The bondage numbers of graphs with small crossing numbers

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. Kang and Yuan proved b(G)?8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.     

A generalization of interval edge-colorings of graphs

An edge-coloring of a graph G with colors 1,2,…,t is called an interval (t,1)-coloring if at least one edge of G is colored by i, i=1,2,…,t, and the colors of edges incident to each vertex of G are distinct and form an interval of integers with no more than one gap. In this paper we investigate some properties of interval (t,1)-colorings. We also determine exact values of the least and the greatest possible number of colors in such colorings for some families of graphs.     

Equitable list coloring of planar graphs without 4- and 6-cycles

A graph G is equitably k-choosable if for any k-uniform list assignment L, there exists an L-colorable of G such that each color appears on at most vertices. Kostochka, Pelsmajer and West introduced this notion and conjectured that G is equitably k-choosable for k>Δ(G). We prove this for planar graphs with Δ(G)≥6 and no 4- or 6-cycles.     

Outerplanar and Planar Oriented Cliques

The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all .     

Counterexamples to Grötzsch-Sachs-Koester's conjecture

Let G be a 4-regular planar graph and suppose that G has a cycle decomposition S (i.e., each edge of G is in exactly on cycle of the decomposition) with every pair of adjacent edges on a face always in different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Grötzsch-Sachs-Koester's conjecture states that if the cycles of G can be partitioned into four classes, such that two cycles in the same classes are disjoint, G is vertex 3-colorable. In this note, the conjecture is disproved.     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.     

Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable

The Total Coloring Conjecture, in short, TCC, says that every simple graph is (Δ+2)-totally-colorable where Δ is the maximum degree of the graph. Even for planar graphs this conjecture has not been completely settled yet. However, every planar graph with Δ≥9 has been proved to be (Δ+1)-totally-colorable. In this paper, we prove that planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable.     

Linear coloring of planar graphs with large girth

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of the graph G is the smallest number of colors in a linear coloring of G. In this paper we prove that every planar graph G with girth g and maximum degree Δ has if G satisfies one of the following four conditions: (1) g≥13 and Δ≥3; (2) g≥11 and Δ≥5; (3) g≥9 and Δ≥7; (4) g≥7 and Δ≥13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6.     

The deficiency of a regular graph

A proper edge coloring c:E(G)→Z of a finite simple graph G is an interval coloring if the colors used at each vertex form a consecutive interval of integers. Many graphs do not have interval colorings, and the deficiency of a graph is an invariant that measures how close a graph comes to having an interval coloring. In this paper we search for tight upper bounds on the deficiencies of k-regular graphs in terms of the number of vertices. We find exact values for 1?k?4 and bounds for larger k.     

(2 + ϵ)‐Coloring of planar graphs with large odd‐girth

The odd‐girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function ƒ(ϵ) for each ϵ : 0 < ϵ < 1 such that, if the odd‐girth of a planar graph G is at least ƒ(ϵ), then G is (2 + ϵ)‐colorable. Note that the function ƒ(ϵ) is independent of the graph G and ϵ → 0 if and only if ƒ(ϵ) → ∞. A key lemma, called the folding lemma, is proved that provides a reduction method, which maintains the odd‐girth of planar graphs. This lemma is expected to have applications in related problems. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 109–119, 2000