Critical Kernel Imperfect Problem in Generalizations of Bipartite Tournaments | Graphs and Combinatorics
Skip to main content
Springer Nature Link
Log in

Critical Kernel Imperfect Problem in Generalizations of Bipartite Tournaments

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Kernel is an important topic in digraphs. A digraph such that every proper induced subdigraph has a kernel is said to be critical kernel imperfect (CKI, for short) if the digraph does not have a kernel. Galeana-Sánchez and Olsen characterized the CKI-digraphs for the following families of digraphs: asymmetric arc-locally in-/out-semicomplete digraphs, asymmetric 3-quasi-transitive digraphs and asymmetric 3-anti-quasi-transitive \(TT_3\)-free digraphs. In this paper, we shall completely characterize the above four classes CKI-digraphs without any restriction on arcs and \(TT_3\)-free subdigraphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Bang-Jensen, J.: Arc-local tournament digraphs: a generalization of tournaments and bipartite tournaments. Department of Mathematics and Computer Science, University of Southern Denmark, Preprint No. 10, (1993)

  2. Bang-Jensen, J.: The structure of strong arc-locally semicomplete digraphs. Discrete Math. 283, 1–6 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bang-Jensen, J., Gutin, G.: Digraphs: Theory. Algorithms and Applications. Springer, London (2000)

    MATH  Google Scholar 

  4. Balbuenna, C., Guevara, M., Olsen, M.: Structural properties of CKI-digraphs. AKCE Int. J. Graphs Comb. 11(1), 67–80 (2014)

    MathSciNet  MATH  Google Scholar 

  5. Chudnovsky, M., Robertson, N., Seymour, P., Thomas, P.: The strong perfect graph theorem. Ann. Math. 164(2), 51–229 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  6. Galeana-Sánchez, H.: Kernels and perfectness in arc-local tournament digraphs. Discrete Math. 306, 2473–2480 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  7. Galeana-Sánchez, H., Goldfeder, I.A.: A classification of all arc-locally semicomplete digraphs. Discrete Math. 312, 1883–1891 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  8. Galeana-Sánchez, H., Goldfeder, I.A., Urrutia, I.: On the structure of 3-quasi-transitive digraphs. Discrete Math. 310, 2495–2498 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  9. Galeana-Sánchez, H., Goldfeder, I.A.: Hamiltonian cycles in a generalition of bipartite tourmaments with a cycle factor. Discrete Math. 315, 135–143 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  10. Galeana-Sánchez, H., Neumann-Lara, V.: On Kernel-perfect critical digraphs. Discrete Math. 59, 257–265 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  11. Galeana-Sánchez, H., Olsen, M.: A Characterization of Locally Semicomplete CKI-digraphs. Graphs Combin. 32, 1873–1879 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  12. Galeana-Sánchez, H., Olsen, M: Solving the kernel perfect problem by (simple) forbidden subdigraphs for digraphs in some families of generalized tournaments and generalized bipartite tournaments, arXiv:1712.00138v5

  13. Galeana-Sánchez, H., Rojas-Monroy, R.: Kernels in quasi-transitive digraphs. Discrete Math. 306, 1969–1974 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  14. Richardson, M.: Solution of irreflective relations. Ann. Math. 58, 573–580 (1953)

    Article  MathSciNet  Google Scholar 

  15. Wang, S., Wang, R.: The structure of strong arc-locally in-semicomplete digraphs. Discrete Math. 309, 6555–6562 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  16. Wang, S., Wang, R.: Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs. Discrete Math. 311, 282–288 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  17. Wang, R.: A conjecture on 3-anti-quasi-transitive digraphs. Discrete Math. 322, 48–52 (2014)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The author thanks the anonymous referees for several helpful comments.

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi, People’s Republic of China

    Ruixia Wang

Authors
  1. Ruixia Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ruixia Wang.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work is supported by the National Natural Science Foundation for Young Scientists of China (11401354)(11501490)(11501341).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wang, R. Critical Kernel Imperfect Problem in Generalizations of Bipartite Tournaments. Graphs and Combinatorics 35, 669–675 (2019). https://doi.org/10.1007/s00373-019-02022-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-019-02022-5

Keywords

Mathematics Subject Classification

Search

Navigation