Recently, Chudnovsky, Cook, Davies, Oum, and Tan obtained the first finite bound on the chromatic number of t-perfect graphs, showing that they are 199053-colorable. We improve this bound to 186 by refining their proof. The original proof establishes that every graph with large odd girth and large chromatic number contains a certain structure called an r-arithmetic rope, and that its existence in a certain leveling of a graph with large odd girth would imply an odd wheel as a t-minor, a known obstruction of t-perfectness. While their technique requires a lower bound on the chromatic number that is exponential in r, we show that the existence of an r-arithmetic rope can already be guaranteed under a linear bound. Using a slightly weakened notion of arithmetic ropes allows us to reduce the bound even further.
We give an explicit simple bridgeless cubic graph on 112 vertices with no Petersen coloring, and hence no normal 5-edge-coloring. The graph is identified by the SHA-256 digest in Theorem 1.1. It is assembled from three copies of a four-pole L and a claw six-pole C; in turn, L is assembled from four copies of a four-pole F and one copy of C, where F is obtained from the Petersen graph by deleting the endpoints of one edge. We give direct SAT formulations for Petersen colorings and normal 5-edge-colorings. CaDiCaL 3.0.1 returned UNSAT for both formulas, and drat-trim verified the resulting DRAT proofs. The ancillary archive contains the construction, an explicit relabeling, the encoders, certificates, hashes, and verification programs. Combined with a theorem of Ma, Mattiolo, Steffen, and Wolf, the counterexample also implies that infinitely many connected simple bridgeless cubic graphs have no Petersen coloring. We also give a separately verified, nonisomorphic $D_3$-symmetric 112-vertex counterexample. We do not address whether 112 is minimum.
An r-dynamic coloring of a graph G is a proper vertex coloring in which each vertex sees at least min{r, d(v)} distinct colors in its neighborhood. The minimum number of colors in such a coloring is the r-dynamic chromatic number χdr(G). We determine exact values and upper bounds of χdr for several graph classes, including triangular grids, planar 3-trees for r ≤ 4, and planar Eulerian triangulations for r ≤ 3 (with a partial result for r = 4), confirming the conjecture of [Song et al. 2014] for these subclasses. We also establish exact values for the 2-dynamic chromatic number of a subclass of circulant graphs, confirming a conjecture of [Montgomery 2001] for this regular family.
Juan Gutiérrez, Grover Ugarte· Anais do XI Encontro de Teor...· 0 citations
A graph is
perfect
if, for every induced subgraph, the chromatic number equals the size of its largest clique. In 1972, Lovász established a fundamental characterization of perfect graphs, showing that a graph is perfect if and only if, for every induced subgraph, the product of the size of the largest independent set and the size of the largest clique is at least the number of vertices. His proof relied on the technique of vertex replication. In this paper, we present an alternative proof of Lovász's result that avoids vertex replication. As vertex replication does not in general preserve ‐perfection, the argument developed here applies to the study of ‐perfect graphs, a class introduced by Ravindra in 2011.
The Petersen coloring conjecture of Jaeger asserts that every bridgeless cubic graph admits a Petersen coloring. Recently, Putman presented an explicit counterexample on $112$ vertices and verified its non-colorability by showing, using a SAT solver, that an instance with $3640$ variables and $68324$ clauses is unsatisfiable. We give a short human-checkable proof that this graph is indeed a counterexample. Our proof determines the coloring behavior of the multipoles used in the construction by means of small explicit finite case analyses and reduces the final contradiction to a simple structural property of the line graph of the Petersen graph. Besides providing a proof that does not rely on a large SAT computation, our approach gives further insight into the gadgets underlying the construction.
A graph has an
‐coloring
if there exists an assignment from the vertices to subsets of with size such that adjacent vertices are assigned disjoint subsets. Odd girth at least is a necessary condition for a graph to have a ‐coloring. Chen and Raspaud conjectured a tight upper bound on the maximum average degree of a graph with odd girth at least that guarantees a ‐coloring. Namely, they conjectured that every graph with odd girth at least and maximum average degree less than has a ‐coloring. This conjecture is true for ; when , computers were used to perform case analysis. The main result of this paper confirms the conjecture for the next open case () without the use of computers. Moreover, our approach yields simpler, computer‐free proofs for previously known cases ().
Ilkyoo Choi· Journal of Graph Theory· 1 citation· ⚡1
A proper conflict-free coloring is a proper vertex coloring in which every nonisolated vertex has a color occurring uniquely in its open neighborhood. We prove that every graph with neither a $K_5$-minor nor a $Q_6$-minor admits such a coloring with at most seven colors, where $Q_6=K_3\vee\overline{K_3}$. In particular, this improves the previous general upper bound of eight for planar graphs. The proof combines a previously developed iterated distance-three selector construction with a general anchor-contraction lifting principle. The first supplies independently colored witnesses in closed neighborhoods, while the second combines those witnesses with a proper coloring of a suitable minor. We also develop the parity analogue of the first mechanism and show that, whenever the $K_{k+1}$ case of Hadwiger's conjecture holds, every $K_{k+1}$-minor-free graph can be proper vertex colored with $2k-1$ colors such that every nonisolated vertex has a color occurring an odd number of times in its open neighborhood.
A. Jiménez, C. N. Lintzmayer, M. Sambinelli· 0 citations