a topological lower bound for the circular chromatic number of schrijver graphs

• DOI: 10.1002/jgt.v49:4
• Publication Date: 2005-04-07
• Authors: Peyman Afshani; Mahya Ghandehari; Hamed Hatami; Mahsa Ghandehari; Ruzbeh Tusserkani; Xuding Zhu
• Keywords: kvocientni grafi; Extremal graph theory; graph theory; 0211 other engineering and technologies; induced subgraphs; 02 engineering and technology; 0102 computer and information sciences; [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; 01 natural sciences; 0101 Pure Mathematics; info:eu-repo/classification/udc/519.17; edge-labelings; FOS: Mathematics; Mathematics - Combinatorics; inducirani podgrafi; 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik; Hamming graphs; mathematics; isometric subgraphs; 004; Erdos-Sos Conjecture; označevanje povezav; 05C15; teorija grafov; matematika; Cartesian products; kartezični produkt grafov; quotient graphs; Combinatorics (math.CO); Hammingovi grafi; izometrični podgrafi

AbstractThis paper proves that if G is a graph (parallel edges allowed) of maximum degree 3, then χ′c(G) ≤ 11/3 provided that G does not contain H1 or H2 as a subgraph, where H1 and H2 are obtained by subdividing one edge of K (the graph with three parallel edges between two vertices) and K4, respectively. As χ′c(H1) = χ′c(H2) = 4, our result implies that there is no graph G with 11/3 < χ′c(G) < 4. It also implies that if G is a 2‐edge connected cubic graph, then χ′c(G) ≤ 11/3. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 325–335, 2005