On the Independence Number of Edge Chromatic Critical Graphs

Autor:	Wenyao Song, Shiyou Pang, Lianying Miao, Zhengke Miao
Jazyk:	angličtina
Rok vydání:	2014
Předmět:	Critical graph Applied Mathematics Edge (geometry) Brooks' theorem Combinatorics Edge coloring edge-chromatic critical graphs Chordal graph QA1-939 Discrete Mathematics and Combinatorics Chromatic scale Graph coloring independence number edge coloring Mathematics Independence number
Zdroj:	Discussiones Mathematicae Graph Theory, Vol 34, Iss 3, Pp 577-584 (2014)
ISSN:	2083-5892
Popis:	In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree ∆ and independence number α(G), α(G) ≤ |V | 2 . It is known that α(G) < 3∆−2 5∆−2 |V |. In this paper we improve this bound when ∆ ≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α(G) ≤ 3∆−3 5∆−3 |V | when ∆ ≥ 5 and n2 ≤ 2(∆− 1).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::be70e45a0b661dc3dc5beec55726916a https://doaj.org/article/becf8327da144f80bd83ffb4561711aa Zobrazit plný text záznamu Plný text ve formátu PDF