Связи различных хроматических характеристик графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

введение.з

Глава I. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ.

§ I. Основные определения теории графов

§ 2. Раскраска графов. Хроматический многочлен графов ••

Глава П. ОДНОЗНАЧНО И ЛОКАЛЬНО ОДНОЗНАЧНО РАСКРАШИВАЕМЫЕ ГРАФЫ.

§ I. Однозначно раскрашиваемые графы с наименьшим числом ребер

§ 2. Класс 1С-деревьев.

§ 3« Элементарные двудольные мультиграфы.

§ 4. Локально однозначно раскашиваемые графы

Глава Ш. ХРОМАТИЧЕСКИЙ МНОГОЧЛЕН ГРАФОВ.

§ I. Хроматически эквивалентные и биэквивалентные графы •

§ 2. Сильно и слабо циклические графы с целочисленными хроматическими спектрами

§ 3. Хроматически единственные графы и классы графов «•••

В настоящее время графы и связанные с ними методы исследований органически цронизывают на разных уровнях едва ли не всю современную математик. Теория графов эффективно используется в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Теория графов находит широкое применение в таких областях црикладной математики, как црограммирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, В то же самое время теория графов вместе со смежным с ней комбинаторным анализом постепенно превращается из набора искусственных цриемов решения отдельных задач в стройный и цельный раздел современной математики.

Одним из центральных разделов теории графов являются задачи раскраски графов, возникшие в связи со знаменитой цроблемой четырех 1фасок (решенной спустя 100 лет Аппелем и Хакеном [9, 10]).

Сама по себе цроблема четырех красок едва ли имеет какие-либо важные приложения. Однако эта проблема сыграла большую роль в развитии всей теории графов. Попытки ее решения цривели, в частности, к продвижению двух следующих направлений: чисто комбинаторной характеризации пленарных графов и изучения хроматических свойств графов общего вида, каждое из которых, как известно, имеет непосредственное применение и в чистой математике, и в практике.

Насколько трудна задача раскраски графов, показывает принадлежность к классу А/Р -полных задач даже таких частных задач, как рас1фашиваемость графа в 3 цвета [4] или раскраска пленарных однородных степени 4 графов [8].

Вряд ли стоит здесь пытаться рассмотреть все направления исследований в рас!фаске графов. Вместо этого лишь укажем направления, к которым принадлежат результаты предлагаемой диссертации: изучение структур однозначно раскрашиваемых или близких к ним по свойствам графов, установление связей между хроматическим многочленом и некоторыми характеристиками графов.

Диссертация состоит из введения и трех глав. Для удобства читателя нумерация теорем и т.д. трехиндексная, новые результаты начинаются с цифры, означающей номер главы, далее идут номер параграфа и порядковый номер соответствующего утверждения, ранее известные результаты начинаются с первых трех букв А, Бг и В русского алфавита, соответственно относящих .эти результаты к одной из трех глав.

1. Зыков А.А. Теория конечных графов. - Новосибирск: Наука, 1969. - 544 с.

2. Зыков А.А. О некоторых свойствах линейных комплексов.-Мат. сборник, 1949, т.24, №2, с. 163-188.

3. Харари Ф. Теория графов. М.: Мир, 1973. - 304 с.

4. Гэри М., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи. М.: Мир, 1982. - 416 с.

5. Bollobas В. Exstremal Graph Theory.- London: Academic Press, 1978.- 488 p.

6. Golumbic M.C. Algorithmic Graph Theory and Perfect Graphs.- Hew York: Academic Press, 1980.- 284 p.

7. Cvetkovic D.,Doob M.,Sachs H. Spectra of Graphs.-Theory and Applications.- Berlin: Deutscher Verl. der V/iss, 1980,- 368 p.

8. Dailey D.P. Uniquenness of colorability and colorabi-lity of planar 4-regular graphs are HP-complete.- Discrete Math., 1980, v.30, no.3, p.289-293.

9. Appel K.,Haken W. Every planar map is four colorable. Part 1s Discharging.- 111.J.Math., 1977, v.21, no.3, p.429-490.

10. Appel K.,Haken W. Every planar map is four colorable. Part 2: Reducibility.-Ill.J.Math.,1977,v.21,no.3,p.491-567.

11. Aksionov V.A.,Mel'nikov L.S. Essay on the theme: The three-color problem.- Combinatorics, v.1. Amsterdam e.a., 1978, p.23-34.

12. Aksionov V.A. On uniquely 3-colorable planar graphs.-Discrete Math., 1977, v.20, no.3, p.209-216.

13. Mel*nikov L.S.»Steinberg R. One counterexample for two conjectures on three coloring.- Discrete Math., 1977, v. 20, no.2, p.203-206.

14. Kleinschmidt P. When is the graph of a triangulation uniquely 4-colorable?- Amer.Math.Mon., 1977, v.84, no.5, p. 366-367.15* Tutte W.T. Hamiltonian circuits.- In: Colloq.int. Teor.Comb. Roma, 1973, v.1. Roma, 1976, p.193-199.

15. Wilson R.J. Some conjectures on edge-colouring of graphs.- In: Recent Adv.Graph Theory: Proc.Symp.Prague 1974. Academia, 1975, p.525-528.

16. Cartwright D.,Harary F, On the coloring of signed graphs.- Elem.Math., 1968, v.23, no.4, p.85-89.

17. Shartrand G.,Geller D. On uniquely colorable planar graphs.- J.Combin.Theory, 1969, v.6, no.3, p.271-287.

18. Harary P.,Hedetniemi S.T.,Robinson R.W. Uniquely colorable graphs.- J.Combin.Theory, 1969,v.6,no.3,p.264-270.

19. Harary P.,Palmer E. On acyclic simplicial complexes.-Mathematika, 1968, v.15, no.1, p.115-122.

20. Beineke L.W.,Pippert R.E. Properties and Characterizations of k-trees.- Mathematika, 1971, v.18, no.1, p.141-151.

21. Rose D.J. On simple characterizations of k-trees.-Discrete Math., 1974, v.7, no.3, p.317-322.

22. Dirac G.A. On rigid circuit graph.- Abh.Math.Sem. Univ.Hamburg, 1961, v.25, no.1-2, p.71-76.

23. Bollobas В» Uniquely colorable graphs.- J.Combin. Theory, 1978, B25, no.1, p.54-61.

24. Nieminen J. A note on uniquele colorable graphs.-Glas.mat., 1974, v.9, no.2, p.193-195.

25. Lovasz L. On the structure of factorizable graphs.-Acta math. Acad.sci.Hung., 1972, v.23, no.1-2, p.179-195.

26. Lovasz L.,Plummer M.D. On minimal elementary bipartite graphs.- J.Combin Theory, 1977, B23,no.1, p.127-138.

27. Tutte W.T. The graph of the chromial of a graph.-bect.Notes Math., 1975, v.452, p*55-6l.

28. Tutte Y/.T. On chromatic polynomials and the golden ratio.- J.Combin.Theory, 1970, v.9, no.3, p.289-296.

29. Bari R.A. Chromatic polynomials and internal and external activities of Tutte.- In: Graph Theory and related topics: Proc.Conf.Honour W.T.Tutte, 1977. Waterloo/Ont., 1979, P.41-52.

30. Balasubramanian K.,Parthasarathy K.R. In search of a complete invariant for graphs.- Lect.Notes Math., 1981, v.885, p.42-59.

31. Godsil C.D.,Gytman I. On the theory of matching polynomial.- J.Combin.Theory, 1981, B5, no.2, p.137-144.

32. Parrel E.J. On general class of graph polynomials.-J.Combin.Theory, 1979, B26, no.1, p.111-122.

33. Birhoff G.D.,Lewis D.C. Chromatic polynomials.-Trans.Amer.Math.Soc., 1946, v.60, no.3, p.355-451.

34. Read R.C. An introduction to chromatic polynomials.-J.Combin.Theory, 1968, v.4, no.1, p.52-71.

35. Tut te W.T. Chromials.- Lect.Notes Math., 1974, v.411, p.243-266.

36. Parrel E.J. Chromatic roots some observations and conjectures.- Discrete Math., 1980, v.29, no.2, p.161-167.

37. Parrel B.J. On chromatic coefficients.- Discrete Math., 1980, v.29, no.3, p.257-264.

38. Meredith G.H.J. Coefficients of chromatic polynomials.- J.Combin.Theory, 1972, v.13, no.1, p.14-17.

39. Woodal D.R. Zeros of chromatic polynomials.- In: Combinatorial surveys: Proc.Sixth.British Combin.Conf.Royal Holloway College, Edham, 1977. London: Academic Press, 1977, p.199-223.

40. Braun K.,Krets M.,Walter M.,Walter В. Die chromatischen Polynome interringfreier graphen.- Manuscr.Math., 1974, v.14, no.3, p.223-234.

41. Berge C. Les problèmes de coloration en theorie des graphes.- Publ.Inst.Stat.Univ.Paris: 1960, v.9, no.2,p.123-160.

42. Hajnal A.,Suranyi J. Über die Aufbösung von Graphen in vollständige Teilgraphen.- Ann.Univ.sei.Budapest Eotvös sect.Math., 1958, v.1, p.113-121.

43. Bari R.A. Chromatically equivalent graphs.- Lee t. Notes Math., 1974, v.406, p.186-200.

44. Chao C.Y.,Whitehead E.G.J. On chromatic equivalence of graphs.- Lect.lTotes Math., 197Q, v.642, p. 121-131.

45. Chao C.Y.,Whitehead E.G.J. Chromatically unique graphs.- Discrete Math., 1979, v.27, no.2, p.171-177.

46. Loerinc B. Chromatic uniqueness of the generalized 9-grah.- Discrete Math., 1978, v.23, no.3, p.313-316.

47. Loerinc B.,Whitehead B.G.J. Chromatic polynomials for regular graphs and modified wheels.- J.Combin.Theory,1981, B31, no.1, p.56-61.

48. Godsil C.D., McKay B. Some computational results on the spectra of graphs.- Lect.Notes Math., 1976, v.560, p.73-92.

49. Mowshowitz A. The Characteristic Polynomial of a graph.- J.Combin.Theory, 1972, B12, no.2, p.177-193.

50. Schwenk A.J. Almost all trees are cospectral.- In: Hew Direction in the Theory of Graphs (F.Harary ed.). Hew York: Academic Press, 1973, p.275-307.

51. Clapham C.R.J., Kleitman D.J. The degree sequences of self-complementary graphs.- J.Combin.Theory, 1976, B20, no.1, p.67-74.

52. Skupien Z. Stirling numbers and colouring of q-tre-es.- Pr.nauk.Inst.mat.PWr., 1977, no.17, p.63-67.

53. Eisenberg B. Characterization of a tree by means of coefficients of the chromatic polynomial.- Trans.New York Acad.Sci., 1972, v.34, no.2, p.146-153.

54. Дмитриев И.Г. Хроматически эквивалентные планарные графы.- 1У-я Всесоюз. конф. по проблемам теоретической кибернетики. Тез. докл. Новосибирск, 1977, с.134-135.

55. Дмитриев И.Г. Характеризация класса 2-деревьев их хроматическими многочленами,- У-я Всесоюз. конф. по проблемам теоретической кибернетики. Тез. дпкл. Новосибирск, 1980, с. 126.

56. Дмитриев И.Г. Слабоциклические графы с целочисленными хроматическими спектрами.- В кн.: Методы дискретного анализа в решении комбинаторных задач. Новосибирск, 1980, вып. 34, с. 3-7.

57. Дмитриев И.Г. Характеризация класса К-деревьев.~ В кн.: Методы дискретного анализа в оценках сложности управляющих систем. Новосибирск, 1982, вып. 38, с. 9-18.

58. Дмитриев И.Г. Минимальная степень однозначно раскрашиваемых графов с наименьшим числом ребер.- В кн.: Машинные методы обнаружения закономерностей, анализа структур и проектирования (Вычислительные системы, вып.92). Новосибирск, 1982, с. 50-55.