On the Independence Number of Edge Chromatic Critical Graphs
In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤. It is known that α (G) < |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 part...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2014-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1753 |
| _version_ | 1797713239326326784 |
|---|---|
| author | Pang Shiyou Miao Lianying Song Wenyao Miao Zhengke |
| author_facet | Pang Shiyou Miao Lianying Song Wenyao Miao Zhengke |
| author_sort | Pang Shiyou |
| collection | DOAJ |
| description | In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤. It is known that α (G) < |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) ≤|V | when △ ≥ 5 and n2 ≤ 2(△− 1) |
| first_indexed | 2024-03-12T07:33:28Z |
| format | Article |
| id | doaj.art-becf8327da144f80bd83ffb4561711aa |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:33:28Z |
| publishDate | 2014-08-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-becf8327da144f80bd83ffb4561711aa2023-09-02T21:42:48ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922014-08-0134357758410.7151/dmgt.1753dmgt.1753On the Independence Number of Edge Chromatic Critical GraphsPang Shiyou0Miao Lianying1Song Wenyao2Miao Zhengke3School of Science, China University of Mining and Technology Xuzhou, Jiangsu, 221008, P.R.ChinaDepartment of Mathematics, Jiangsu Normal University, Xuzhou, Jiangsu, 221116, P.R.ChinaSchool of Science, China University of Mining and Technology Xuzhou, Jiangsu, 221008, P.R.ChinaDepartment of Mathematics, Jiangsu Normal University, Xuzhou, Jiangsu, 221116, P.R.ChinaIn 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤. It is known that α (G) < |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) ≤|V | when △ ≥ 5 and n2 ≤ 2(△− 1)https://doi.org/10.7151/dmgt.1753edge coloringedge-chromatic critical graphsindependence number |
| spellingShingle | Pang Shiyou Miao Lianying Song Wenyao Miao Zhengke On the Independence Number of Edge Chromatic Critical Graphs Discussiones Mathematicae Graph Theory edge coloring edge-chromatic critical graphs independence number |
| title | On the Independence Number of Edge Chromatic Critical Graphs |
| title_full | On the Independence Number of Edge Chromatic Critical Graphs |
| title_fullStr | On the Independence Number of Edge Chromatic Critical Graphs |
| title_full_unstemmed | On the Independence Number of Edge Chromatic Critical Graphs |
| title_short | On the Independence Number of Edge Chromatic Critical Graphs |
| title_sort | on the independence number of edge chromatic critical graphs |
| topic | edge coloring edge-chromatic critical graphs independence number |
| url | https://doi.org/10.7151/dmgt.1753 |
| work_keys_str_mv | AT pangshiyou ontheindependencenumberofedgechromaticcriticalgraphs AT miaolianying ontheindependencenumberofedgechromaticcriticalgraphs AT songwenyao ontheindependencenumberofedgechromaticcriticalgraphs AT miaozhengke ontheindependencenumberofedgechromaticcriticalgraphs |